#include <bits/stdc++.h>

using i64 = long long;

std::vector<int> f;

void init(int n)
{
    const int inf = 1e9;
    f.assign(n + 1, inf);
    std::vector<std::pair<int, int>> a;
    for (int i = 1; i * (i + 1) / 2 <= n; ++i)
    {
        a.emplace_back(i * (i + 1) / 2, i);
    }

    f[0] = -1;
    for (int i = 1; i <= n; ++i)
    {
        for (auto &[x, y] : a)
        {
            if (x > i)
            {
                break;
            }

            f[i] = std::min(f[i], f[i - x] + y + 1);
        }
    }
}

void solve()
{
    int k;
    std::cin >> k;
    std::cout << f[k] << "\n";
}

int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    int t = 1;
    init(2e5);
    std::cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
